1. Field of the Invention
The invention relates to an Internet Protocol (IP) address lookup method used in routers, particularly to a lookup method to obtain IP address with multi-level forwarding table.
2. Description of Related Art
Because of the fast development of Internet and the network traffic flow tending to be unpredictable, the original 80/20 rule (80% traffic flow in local area network and 20% traffic flow in wide area network) is no longer applied, adding that the emerging Gigabit Ethernet make router become the bottleneck of the network performance. By and large, there's a Routing Table inside the router, which includes the connectivity data among networks for router to perform the routing information processing in accordance with the table during packet switching. However, as router needs to consume lots of resources during Routing Information Processing, it is one of the major reasons to slow down the speed of router. To increase the Layer 3 (Network Layer) packet switching processing performance, as a result, the routing search capability must be effectively elevated.
For each entered packet, router must count on the destination address in the routing table to execute IP address search once to decide to where the next hop shall be sent. Each item in the routing table includes destination address/network mask and output port number. In view of the introduction of CIDR technology, items in routing table is defined as prefix/prefix length and output port number and the prefix length is limited in between 0 and 32.
IP address search mechanism is to conduct the search of the longest prefix matching in the routing table of router in terms of the destination address of each entered packet so that the corresponding next hop can be located. As the process is sort of complicated, most of routers today all employ software to operate. Whereas the conversion speed can't satisfy the huge flow in the current network, this also makes the IP address search become the major bottleneck of current network.
The conventional method for improving the lookup capability of router is the indirect lookup. The method first assumes a corresponding binary trees 12 in accordance with the prefix in the routing table and defines the IP address occupied by each prefix. Then construct a segment array and a plurality of next hop array and IP address lookup algorithm is that utilizes the index of the segment array to find out the corresponding next hop of the packet.
An embodiment using the indirect lookup method is shown in FIGS. 1(a) to 1(c). FIG. 1(a) shows that ten prefixes (number A to J) in the routing table are visualized to the corresponding binary tries structure. FIG. 1(b) defines the IP addresses taken by each prefix (number A to J). FIG. 1(c) separates the prefix into two nibbles. The most significant nibble is used for the address of segment array 13 and the less significant nibble is used for the addresses of a plurality of next hop arrays 14, 14′ and 14″. The contents of the segment array 13 and the plurality of next hop arrays 14˜14″ are filled in accordance with the IP address occupied by the prefix of Number A to J. For example, the first column of the segment array 13 records next hop (when the bit number of the prefix is less than 4) or points to the pointers of next hop arrays 14˜14″, the second column is the longest offset k (bit number of the prefix minus 4) of the corresponding prefix of the pointer, and the corresponding next hop arrays 14˜14″ of the pointer has 2k contents. The next hop arrays 14˜14″ has only one column for recording the next hop. After constructing the contents of the segment array 13 and plurality of next hop arrays 14˜14″, IP address lookup algorithm can use IP address of packet along with the instruction of the segment array 13 and next hop array 14˜14″ to find out the corresponding next hop of the packet.
However, the segment array 13 and plurality of next hop arrays 14˜14″ of the said indirect lookup method is not flexible in operation and require lots of memories.
Another method for improving the lookup capability of router is declared in the patent description of the Patent Publication No. 410292 of Republic of China, entitled “Method and system for routing information construction and IP routing lookup applied in ultra high speed switching router”. Such method ensures that the lookup times of output port during packet switching won't exceed 3 times with compression means and confines the size of the forwarding table to be lower than 512 KB. Whereas, the said compression method is very complicated and the corresponding forwarding table must be rebuilt to obtain the most complete routing table when the connection of router changes, causing operation extremely inconvenient.
In summary, to satisfy more and more users using network capable of swiftly operating, how to build up the router with high transmission efficiency is actually a very important subject for the time being.